#include "Vector.hh"
#include <utility>

//*只读访问接口

Rank Vector::find(int const &e, Rank lo, Rank hi){
    while ((lo<hi--)&&(_elem[hi]!=e));
    return hi;  
}


//*可写访问接口

Rank Vector::insert(Rank r, int const &e){
    expand();
    for(int i=_size;i>r;i--){
        _elem[i]=_elem[i-1];
    }
    _size++;
    return r;
}
int Vector::remove(Rank lo, Rank hi){
    if(lo==hi) return 0;
    while(hi<_size){
        _elem[lo++]=_elem[hi++];
    }
    _size=lo;
    return hi-lo;
}
int Vector::deduplicate(){
    int old_size=_size;
    int i=0;
    while(i<_size){
        if(find(_elem[i],0,i)<0)
            i++;
        else
            remove(i);
    }
    return old_size-_size;
}


void Vector::expand()
{
    if (_size < _capacity)
        return; //尚未满员时，不必扩充
    _capacity = std::max(_capacity,DEFAULT_CAPACITY);
    int *oldElem=_elem;_elem=new int[_capacity*2];
    for(int i=1;i<_size;i++)
        _elem[i]=oldElem[i];
    delete[] oldElem;
}

void Vector::copyFrom(int const *A, Rank lo, Rank hi ){
    _elem=new int[_capacity];
    for(int i=0; i<_size;i++){
        _elem[i]=A[lo+i];
    }
}
/*! 排序算法
 */

//*冒泡排序
void Vector::bubbleSort(Rank lo, Rank hi)
{
    for(Rank last=--hi;lo<hi;hi=last)//循环开始前执行了--hi
        for(Rank i=last=lo;i<hi;i++)//每次扫描开始前将 last 初始化为 lo
            if(_elem[i]>_elem[i+1]){
                std::swap(_elem[i],_elem[i+1]);
                last=i;
            }
}
//*二路归并
void Vector::merge(Rank lo, Rank mi, Rank hi)
{
	//准备工作
    Rank i=0;T *A=_elem+lo;//A为_elem[lo,mi)
    Rank j=0, lb=mi-lo;T *B=new T[lb];//将A的前缀拷贝到B
    for(Rank i=0;i<lb;i++){
        B[i]=A[i];
    }
	Rank k=0,lc=hi-mi;T *C=_elem+mi;//C为_elem[mi,hi)
	//开始归并
	while (j<lb&&k<lc) {
		A[i++]=(B[j]<C[k])?B[j++]:C[k++];
	}
	while (j<lb) {
		A[i++]=B[j++];
	}
    delete [] B;
    
}
//*归并排序
void Vector::mergeSort(Rank lo, Rank hi){
    if(hi-lo<2) return;
    Rank mi=lo+(hi-lo)/2;
    mergeSort(lo, mi);
    mergeSort(mi, hi);
    merge(lo, mi, hi);
}